package com.yuufa.test.sort;

import com.yuufa.util.Tool;

public class SortMain {

    public static void main(String[] args) {
        
    }
}

class BinarySearch {
    
    public static void test() {
        int n = 5;
        int[] s = Tool.random(n);
        int key = s[0];
        
        Insert.sort(s, n);
        Tool.output(s, 0, n-1);
        
        search(s, 0, n-1, 1, key);
    }
    
    public static void test1() {
        int n = 9;
        int[] s = Tool.random(n);
        int key = 40;
        
        Insert.sort(s, n);
        Tool.output(s, 0, n-1);
        
        loopSearch(s, 0, n-1, key);
    }
    
    public static void loopSearch(int[] s, int left, int right, int key) {
        
        boolean finish = false;
        
        while(left <= right && !finish) {
            int middle = (left + right) / 2;
            
            if(s[middle] == key) {
                System.out.println(String.format("key[%d]'s index:%d", key, middle));
                finish = true;
            } else {
                if(s[middle] < key) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
        }
        
        if(!finish) {
            System.out.println("not found key:" + key);
        }
    }
    
    public static void search(int[] s, int left, int right, int count, int key) {
        
        if(left <= right) {
            int middle = (left + right) / 2;
            
            if(s[middle] == key) {
                System.out.println(String.format("key[%d]'s index:%d, compare count:%d", key, middle, count));
            } else {
                if(s[middle] < key) {
                    search(s, middle+1, right, count+1, key);
                } else {
                    search(s, left, middle-1, count+1, key);
                }
            }
        } else {
            System.out.println(String.format("not found key[%d]'s index:%d, compare count:%d", key, -1, count));
        }
    }
}

class Quick {
    
    public static void test() {
        int[] s = Tool.random(10);
        int n = s.length;

        sort(s, 0, n-1, n);

        Tool.output(s, 0, n - 1);
    }
    
    public static void sort(int[] s, int left, int right, int n) {
        
        if(left <= right) {
            int k = partition(s, left, right, n);
            sort(s, left, k-1, n);
            sort(s, k+1, right, n);
        }
    }
    
    public static int partition(int[] s, int left, int right, int n) {
        
        int pivot = s[left];
        int i = left;
        int j = right + 1;
        
        while(i<j) {
            while(++i<=right && s[i] < pivot);
            while(--j>=left && s[j] > pivot);
            
            if(i<j) {
                int t = s[i];
                s[i] = s[j];
                s[j] = t;
            }
        }
        
        // return j;
        s[left] = s[j];
        s[j] = pivot;
        
        Tool.output(s, 0, n-1);
        
        return j;
    }
}

class Heap {
    
    public static void test() {
        int n = 10;
        int[] s = Tool.randomHeap(n);

        sort(s, n);

        Tool.output(s, 1, n);
    }
    
    public static void sort(int[] s, int n) {
        
        for(int i=n/2;i>=1;i--) {
            shift(s, i, n);
        }
        
        int t = s[1];
        s[1] = s[n];
        s[n] = t;
        
        for(int i=n-1;i>=2;i--) {
            shift(s, 1, i);
            
            t = s[1];
            s[1] = s[i];
            s[i] = t;
        }
        
    }
    
    public static void shift(int[] s, int index, int n) {
        
        int t = s[index];
        int j = index * 2;
        
        while(j<=n) {
            if(j<n) {
                if(s[j] < s[j+1]) {
                    j++;
                }
            }
            
            if(t < s[j]) {
                s[j/2] = s[j];
                j = j * 2;
            } else {
                break;
            }
        }
        
        s[j/2] = t;
    }
}

class Select {

    public static void test() {
        int[] s = Tool.random(10);
        int n = s.length;

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = 0; i < n; i++) {
            int t = s[i];
            int j = i;

            for (int k = i + 1; k < n; k++) {
                if (s[j] > s[k]) {
                    j = k;
                }
            }

            s[i] = s[j];
            s[j] = t;
            
            Tool.output(s, 0, n-1);
        }
    }
}

class Shell {

    public static void test() {
        int[] s = Tool.random(10);
        int n = s.length;

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int t = s[i];
                int j = i - gap;

                while (j >= 0 && t < s[j]) {
                    s[j + gap] = s[j];
                    j -= gap;
                }

                s[j + gap] = t;
            }

            Tool.output(s, 0, n - 1);
        }
    }
}

class Insert {

    public static void test() {
        int[] s = Tool.random(10);
        int n = s.length;

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = 1; i < n; i++) {
            int t = s[i];
            int j = i - 1;

            while (j >= 0 && t < s[j]) {
                s[j + 1] = s[j];
                j--;
            }

            s[j + 1] = t;

            // Tool.output(s, 0, n-1);
        }
    }
}

class Merge {
    
    public static void test() {
        int n1 = 3;
        int[] s1 = Tool.random(n1);
        Bubble.sort(s1, n1);
        
        int n2 = 4;
        int[] s2 = Tool.random(n2);
        Bubble.sort(s2, n2);
        
        int[] dest = sort(s1, n1, s2, n2);
        Tool.output(dest, 0, n1 + n2 - 1);
    }
    
    public static int[] sort(int[] s1, int n1, int[] s2, int n2) {
        
        int[] dest = new int[n1 + n2];
        
        int i = 0;
        int j = 0;
        int k = 0;
        
        while( i < n1 && j < n2) {
            if(s1[i] < s2[j]) {
                dest[k++] = s1[i++];
            } else {
                dest[k++] = s2[j++];
            }
        }
        
        while( i < n1) {
            dest[k++] = s1[i++];
        }
        
        while( j < n2) {
            dest[k++] = s2[j++];
        }
        
        return dest;
    }
}

class Bubble {

    public static void test() {
        int[] s = Tool.random(10);
        int n = s.length;

        sort(s, n);

        Tool.output(s, 0, n - 1);
    }

    public static void sort(int[] s, int n) {

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (s[j] > s[j + 1]) {
                    int t = s[j];
                    s[j] = s[j + 1];
                    s[j + 1] = t;
                }
            }

            // Tool.output(s, 0, s.length - 1);
        }
    }
}
